/*
 * @Author: liusheng
 * @Date: 2022-06-05 10:46:31
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-05 18:29:15
 * @Description: 剑指 Offer II 072. 求平方根
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 072. 求平方根
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

 

示例 1:

输入: x = 4
输出: 2
示例 2:

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
 

提示:

0 <= x <= 2^31 - 1

注意：本题与主站 69 题相同： https://leetcode-cn.com/problems/sqrtx/

通过次数17,327  提交次数41,310
 */

/*
二分法
*/
class Solution {
public:
    int mySqrt(int x) {
        if (!x)
        {
            return x;
        }

        int first = 0;
        int step = 0;
        int iter = 0;
        int count = x;
        while (count > 0)
        {
            iter = first;
            step = count / 2;
            iter += step;
            if (iter < (double)x/iter)
            {
                first = ++iter;
                count -= (step + 1);
            }
            else
            {
                count = step;
            }
        }

        return first == x / first ? first : first - 1;
    }
};

/*
二分改进
*/
class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1)
        {
            return x;
        }
        
        int first = 0;
        int step = 0;
        long iter = 0;
        int count = x;
        int result = 0;
        while (count > 0)
        {
            iter = first;
            step = count / 2;
            iter += step;
            // because of truncated,so <= not <
            if (iter * iter <= x)
            {
                result = iter;
                first = ++iter;
                count -= (step + 1);
            }
            else
            {
                count = step;
            }
        }
        
        return result;
    }
};

/*
牛顿迭代法
*/
#include<cmath>
class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1)
        {
            return x;
        }
    
        //牛顿迭代法:X_k+1 = 1/2 * (X_k + x/X_k)
        //其中x为要求平方根的数
        double root = x;
        while (abs(root * root - x) > 0.1 )
        {
            root = (root + x / root) / 2.0;
        }
        
        return (int) root;
    }
};
